package offer2

/**
原题链接:
https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/description/?envType=study-plan-v2&envId=coding-interviews

B站 小道仙97
剑指offer 62.圆圈中最后剩下的数字

0,1,2......n-1这n个数组排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字，
求出这个圆圈里剩下的最后一个数字。

例如：0，1，2，3,4，这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，
则删除的前4个数字依次是2，0，4，1，因此最后剩下的数字是3

示例：
输入:n=5,m=3
输出；3
*/

func lastRemaining(n int, m int) int {
	list := make([]int, n) //声明数组, 每个位置赋值为i
	for i := 0; i < n; i++ {
		list[i] = i
	}

	cur := -1
	for len(list) > 1 { //只要数组还有元素, 持续循环
		cur += m              //累加
		if cur >= len(list) { //如果超过数组长度, 进行取模
			cur = cur % len(list)
		}
		list = append(list[:cur], list[cur+1:]...) //剔除当前元素
		cur--                                      //游标后移一位
	}

	return list[0] //返回最后一位元素
}
